/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Interface;

import java.awt.Color;
import java.awt.Graphics2D;
import java.util.Vector;
import moteur.carte.Clickable;

/**
 * Quadtree, arbre à 4 fils qui partitionne [0 ; 1][0 ; 1] en 4 par le milieu.
 * Permet d'accélérer les détections des collisions dans le cas moyen. Chaque élément
 * est placé dans le plus petit noeud le contenant entièrement.
 * Dans le pire des cas, c'est plus mauvais qu'en linéaire pur.
 * @author Anonyme
 */
public class Quadtree {

    private static final int HAUT_GAUCHE = 0, HAUT_DROIT = 1,
            BAS_GAUCHE = 2, BAS_DROIT = 3;
    private float x, y, delta;
    private Quadtree[] fils = new Quadtree[4];
    private Vector<Clickable> truc = new Vector<Clickable>(2, 1);

    /**
     * Constructeur d'un quadtree vide.
     */
    public Quadtree() {
        delta = 0.25f;
        x = 0.5f;
        y = 0.5f;
    }

    private Quadtree(float nx, float ny, float d, int pos) {
        switch(pos){
            case HAUT_GAUCHE:
        x = nx - d;
        y = ny - d;
                break;
            case HAUT_DROIT:
        x = nx + d;
        y = ny - d;
                break;
            case BAS_GAUCHE:
        x = nx - d;
        y = ny + d;
                break;
            case BAS_DROIT:
        x = nx + d;
        y = ny + d;
                break;
        }
        delta = d * 0.5f;
    }

    private boolean auCentre(Clickable c) {
        float mx = c.getX();
        float my = c.getY();
        float w = c.getWidth();
        return ((x >= mx) && (x <= mx + w)) || ((y >= my) && (y <= my + w));
    }

    /**
     * Tente d'ajouter un clickable à l'arbre.
     * @param c
     * @return False en cas d'échec, True sinon.
     */
    private void add(Clickable c) {

        float mx = c.getX();
        float my = c.getY();
        float w = c.getWidth();
        if (auCentre(c)) {
            truc.add(c);
        } else{

            int i;
            if (mx <= x) {
                if (my <= y) {
                    i = HAUT_GAUCHE;
                } else {
                    i = BAS_GAUCHE;
                }
            } else {
                if (my <= y) {
                    i = HAUT_DROIT;
                } else {
                    i = BAS_DROIT;
                }
            }

            if(fils[i] == null){
            fils[i] = new Quadtree(x, y, delta, i);
            }
            fils[i].add(c);
        }
    }

    public boolean addClickable(Clickable c){

        if(Collide(c)){
            return false;
        }else{
        if (c == null) return true;
        this.add(c);
        return true;
        }

    }
    private boolean Collide(Clickable c){
        if (c == null) return false;
        float mx = c.getX();
        float my = c.getY();
        float w = c.getWidth();
        boolean b = false;

        
        for(Clickable cl: truc){
            if(c.collideWith(cl)) return true;
            }
        if(auCentre(c)){
        for(Quadtree q : fils){
            if((q != null) && !b){
                b = q.Collide(c);
            }
        }
        return b;

        }else{
        Quadtree q;
        if (mx <= x) {
            if (my <= y) {
                q = fils[HAUT_GAUCHE];
            } else {
                q = fils[BAS_GAUCHE];
            }
        } else {
            if (my <= y) {
                q = fils[HAUT_DROIT];
            } else {
                q = fils[BAS_DROIT];
            }
        }
        if (q != null) {
            return q.Collide(c);
        }else{
        return false;
        }
        }
    }

    /**
     * Renvoie un clickable s'il est à la position donnée.
     * @param mx
     * @param my
     * @return
     */
    public Clickable getClickable(float mx, float my) {

        for (Clickable c : truc) {
            if (c.collision(mx, my)) {
                return c;
            }
        }
        Quadtree q;
        if (mx <= x) {
            if (my <= y) {
                q = fils[HAUT_GAUCHE];
            } else {
                q = fils[BAS_GAUCHE];
            }
        } else {
            if (my <= y) {
                q = fils[HAUT_DROIT];
            } else {
                q = fils[BAS_DROIT];
            }
        }
        if (q != null) {
            return q.getClickable(mx, my);
        }else{
        return null;
        }
    }

    /**
     * Retire un clickable de l'arbre.
     * @param c
     */
    public void removeClickable(Clickable c) {
        if (!truc.remove(c)) {

            float mx = c.getX(), my = c.getY();
            Quadtree q;
            if (mx <= x) {
                if (my <= y) {
                    q = fils[HAUT_GAUCHE];
                } else {
                    q = fils[BAS_GAUCHE];
                }
            } else {
                if (my <= y) {
                    q = fils[HAUT_DROIT];
                } else {
                    q = fils[BAS_DROIT];
                }
            }
            if (q != null) {
                q.removeClickable(c);
            }
        }
        this.clean();
    }

    /**
     *
     * @param mx
     * @param my
     */
    public void removeClickableAt(float mx, float my){
        for (Clickable c : truc) {
            if (c.collision(mx, my)) {
                truc.remove(c);
            }
        }
        Quadtree q;
        if (mx <= x) {
            if (my <= y) {
                q = fils[HAUT_GAUCHE];
            } else {
                q = fils[BAS_GAUCHE];
            }
        } else {
            if (my <= y) {
                q = fils[HAUT_DROIT];
            } else {
                q = fils[BAS_DROIT];
            }
        }
        if (q != null) {
            q.removeClickableAt(mx, my);
        }

    }

    @Override
    protected void finalize() throws Throwable {
        super.finalize();
    }



    /**
     * Coupe les branche morte. P-e inutile dans notre cas.
     */
    private void clean() {

        for (Quadtree q : fils) {
            if (q != null) {
                q.clean();
                if (q.isEmpty()) {
                    q = null;
                }
            }
        }
    }
    private boolean isLeaf(){
                for (Quadtree q : fils) {
                if (q != null) {
                    return false;
                }
            }
            return true;
    }
    private boolean isEmpty() {
        if (truc.isEmpty()) {
            for (Quadtree q : fils) {
                if (q != null) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

    /**
     * Pour tester en console.
     */
    public void imprime(){

        System.out.println(x+y);
        
        for (Clickable c : truc) {
            if(c != null) System.out.println(c.toString());
            }

        System.out.println("HAUT_GAUCHE :");
        if(fils[HAUT_GAUCHE] != null) fils[HAUT_GAUCHE].imprime();
        System.out.println("HAUT_DROITE :");
        if(fils[HAUT_DROIT] != null) fils[HAUT_DROIT].imprime();
        System.out.println("BAS_GAUCHE :");
        if(fils[BAS_GAUCHE] != null) fils[BAS_GAUCHE].imprime();
        System.out.println("BAS_DROITE :");
        if(fils[BAS_DROIT] != null) fils[BAS_DROIT].imprime();

    }
    public void draw(Graphics2D g, float xmin, float xmax, float yMin, float yMax, int taille){
        g.setColor(Color.MAGENTA);

            g.drawLine((int)(x*taille), (int)(yMin*taille), (int)(x*taille), (int)(yMax*taille));
            g.drawLine((int)(xmin*taille), (int)(y*taille), (int)(xmax*taille), (int)(y*taille));


        if(fils[BAS_DROIT]!= null) fils[BAS_DROIT].draw(g, x, xmax, y, yMax, taille);
        if(fils[BAS_GAUCHE]!= null) fils[BAS_GAUCHE].draw(g, xmin, x, y, yMax, taille);
        if(fils[HAUT_DROIT]!= null) fils[HAUT_DROIT].draw(g, x, xmax, yMin, y, taille);
        if(fils[HAUT_GAUCHE]!= null) fils[HAUT_GAUCHE].draw(g, xmin, x, yMin, y, taille);
        


    }

}
